"""
队列 (queue) 是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，
而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。
进行插入操作的端称为队尾，进行删除操作的端称为队头。
队列符合先进先出[FIFO]的原则
队列属于常见的一种线性结构，对于出队和进队而言，时间复杂度都为 O(1)
"""


class Node(object):
    def __init__(self, elem, next=None):
        self.elem = elem    # 对应的元素值
        self.next = next    # 表示下一个结点的链点


class Queue(object):
    def __init__(self):
        self.head = None    # 头部结点置为空
        self.rear = None    # 尾部结点置为空

    def is_empty(self):
        # 判断队列是否为空，只要判断头结点是否为None即可
        return self.head is None

    def enqueue(self, elem):
        p = Node(elem)      # 初始化一个新的链点
        if self.is_empty():
            # 如果队列为空，队列头、尾部均为新的链点
            self.head = p
            self.rear = p
        else:
            # 把队列的尾结点的后继结点指向新链点
            self.rear.next = p
            # 新链点作为队列的尾结点
            self.rear = p

    def dequeue(self):
        if self.is_empty():
            # 队列为空，无法执行删除操作
            print("Queue is empty!")
        else:
            result = self.head.elem
            self.head = self.head.next
            return result

    def peek(self):
        if self.is_empty():
            # 队列为空，说明没有元素，打印Not Found
            print("Not Found!")
        else:
            # 返回头结点对应的元素值
            return self.head.elem

    def print_queue(self):
        # 打印队列
        print("queue: ")
        temp = self.head
        myqueue = []
        while temp is not None:
            myqueue.append(temp.elem)
            temp = temp.next
        print(myqueue)



